package binarytree

func preorderTraversal(root *TreeNode) []int {

	if root == nil {
		return nil
	}

	res := []int{}

	res = append(res, root.Val)
	res = append(res, preorderTraversal(root.Left)...)
	res = append(res, preorderTraversal(root.Right)...)

	return res

}

func preorderTraversal2(root *TreeNode) []int {

	res := []int{}

	if root == nil {
		return res
	}

	stack := []*TreeNode{root}

	for len(stack) != 0 {
		temp := stack[len(stack)-1]
		res = append(res, temp.Val)
		stack = stack[:len(stack)-1]

		if temp.Right != nil {
			stack = append(stack, temp.Right)
		}
		if temp.Left != nil {
			stack = append(stack, temp.Left)
		}
	}

	return res

}
